package com.atcumt.Write.writeStructures;

import java.util.Arrays;


public class KMPTest {

    public static void main(String[] args) {

        String desStr = "BABABACABABCABAABD"; // 主串
        String subStr = "ABABCABAAB"; // 模式串

        int[] next = getNext(subStr);
        System.out.println(Arrays.toString(next));

        int index = kmpfunc(desStr,subStr);
        System.out.println(index);
    }

    private static int[] getNext(String subStr) {
        int n = subStr.length();
        int[] next = new int[n];
        int j = -1, y = 0;
        next[0] = -1;

        while (y < n - 1) {
            if (j == -1 || subStr.charAt(j) == subStr.charAt(y)) {
                y++;
                j++;
                next[y] = j;
            } else {
                j = next[j];
            }
        }
        return next;
    }

    private static int kmpfunc(String desStr, String subStr) {
        int x = 0, y = 0;
        int[] next = getNext(subStr);

        while (x < desStr.length() && y < subStr.length()) {
            if (y == -1 || subStr.charAt(y) == desStr.charAt(x)) {
                x++;
                y++;
            } else {
                y = next[y];
            }
        }
        if (y == subStr.length()) {
            return x - y;
        } else {
            return -1;
        }
    }
}